﻿using System;
using System.Collections.Generic;

namespace CrossEntropyProject
{
    public static class MyKmeans
    {

        #region Cluster
        public static KMeansResults Cluster(double[][] objects, int numOfClusters, double[][] initialCentroids = null)
        {
            bool hasChanges = true;
            int iteration = 0;
            int maxIterations = 20;
            Int32 numData = objects.Length;//number of objects
            int numAttributes = objects[0].Length;//number of attributes in each vector of object
            double[][] centroids;//the centroids
            int[] clustering = new int[objects.Length];//holds the clustering for each object

            double totalCost = 0;
            double totalCostLastIteration = -1;

            Int32[] clusterItemCount = new Int32[numOfClusters];//this array holds the number of objects in each cluster

            var randomInitializedResultList = new List<KmeansIterationResult>();

            if (initialCentroids == null)// if no initial centroids were provided then create a random initial clustering assignment
            {

                for (int i = 0 ; i < 10 ; i++)

                {
                    iteration = 0;
                    hasChanges = true;
                    centroids = generateRandomCentroids(numOfClusters, numAttributes);
                    
                    // Perform the clustering until there is no change
                    while (hasChanges && iteration < maxIterations)
                    {
                        if (DataSet.mainForm.backgroundWorker3.CancellationPending)
                        {
                            Constants.crossEntropyCancelFlag = true;
                            break;
                        }

                        totalCost = AssignObjects(objects, centroids, ref clustering, ref clusterItemCount);

                        if (totalCost.Equals(totalCostLastIteration))
                        {
                            hasChanges = false;
                        }
                        else
                        {
                            totalCostLastIteration = totalCost;
                            CalculateNewCentroids(clusterItemCount, ref centroids, objects, ref clustering);
                        }
                        iteration++;
                    }

                    KmeansIterationResult iterationResult = new KmeansIterationResult(numOfClusters, numAttributes);

                    for (int j = 0; j < centroids.Length; j++)
                    {
                        Array.Copy(centroids[j], iterationResult.centroids[j],centroids[j].Length);
                    }

                    iterationResult.objFuncVal = totalCost;

                    randomInitializedResultList.Add(iterationResult);

                }//for
                
                randomInitializedResultList.Sort();

                return new KMeansResults(randomInitializedResultList[0].centroids, clustering);//return the best centroids

            }
            else if (initialCentroids.Length == numOfClusters)//if initial centroids OK
            {
                centroids = initialCentroids;
                // Perform the clustering until there is no change
                while (hasChanges && iteration < maxIterations)
                {
                    if (DataSet.mainForm.backgroundWorker3.CancellationPending)
                    {
                        Constants.crossEntropyCancelFlag = true;
                        break;
                    }
                    totalCost = AssignObjects(objects, centroids, ref clustering, ref clusterItemCount);

                    if (totalCost.Equals(totalCostLastIteration))
                    {
                        hasChanges = false;
                    }
                    else
                    {
                        totalCostLastIteration = totalCost;
                        CalculateNewCentroids(clusterItemCount, ref centroids, objects, ref clustering);
                    }
                    iteration++;
                }
                return new KMeansResults(centroids, clustering);
            }
            else
            {
                return null;//error : the number of initialCentroids does not match the number of clusters
            }
           
        }
        #endregion

        #region CalculateNewCentroids
        private static void CalculateNewCentroids(Int32[] clusterItemCount, ref double[][] centroids, double[][] objects, ref int[] clustering)
        {
            double[][] sums = new double[centroids.Length][];

            //allocate memory
            for (int i = 0; i < sums.Length; i++)
            {
                sums[i] = new double[objects[0].Length];
            }
            //calculate the means for each cluster : first calculate the sums  
            for (int i = 0; i < clustering.Length; i++)
            {
                for (int j = 0; j < sums[clustering[i]].Length; j++)
                {
                    sums[clustering[i]][j] += objects[i][j];
                }
            }

            //second: divide by the number of objects in each cluster
            for (int i = 0; i < sums.Length; i++)
            {
                for (int j = 0; j < sums[i].Length; j++)
                {
                    if (clusterItemCount[i] == 0) //there is no items in this cluster! (can't divide by zero)
                    {
                        sums[i][j] = -1;
                    }
                    else
                    {
                        sums[i][j] /= clusterItemCount[i];
                    }

                }
            }

            //now copy the means to the centroids array

            for (int i = 0; i < sums.Length; i++)
            {
                Array.Copy(sums[i], centroids[i], sums[i].Length);
            }

        }
        #endregion

        #region AssignObjects(double[][] objects, double[][] centroids, ref int[] clustering, ref Int32[] clusterItemCount)
        private static double AssignObjects(double[][] objects, double[][] centroids, ref int[] clustering, ref Int32[] clusterItemCount)
        {
            int objectBelongToCentroidIndex = 0;
            double sumOfDistances = 0;

            Array.Clear(clusterItemCount, 0, clusterItemCount.Length);

            for (int i = 0; i < objects.Length; i++) //for each object
            {
                double minDistance = double.MaxValue;
                for (int j = 0; j < centroids.Length; j++)//for each centroid
                {
                    double distance = CalculateDistance(objects[i], centroids[j]);// temp = d(X,c_i)
                    if (distance < minDistance)
                    {
                        minDistance = distance;
                        objectBelongToCentroidIndex = j;
                    }
                }
                clusterItemCount[objectBelongToCentroidIndex]++;
                clustering[i] = objectBelongToCentroidIndex;
                sumOfDistances += minDistance;
            }
            return sumOfDistances;
        }
        #endregion

        #region generateRandomCentroids(int numOfCentroids, int centroidSize)
        private static double[][] generateRandomCentroids(int numOfCentroids, int centroidSize) 
        {
            var rnd = new Random();
            double[][] centroids = AllocateMemory(numOfCentroids, centroidSize);

            if (numOfCentroids <= 0 || centroidSize <=0 )
            {
                return null;
            }

            //select centroids components randomly
            for (int i = 0; i < numOfCentroids; i++)
            {
                for (int j = 0; j < centroidSize; j++)
                {
                    centroids[i][j] = rnd.NextDouble();
                }
            }

            return centroids;

        }
        #endregion

        #region InitializeClustering(int numData, int clusterCount, ref double[][] centroids)
        //private static int[] InitializeClustering1(int numOfObjects, int numOfClusters, ref double[][] centroids, double[][] objects)
        //{
        //    var rnd = new Random();
        //    var clustering = new int[numOfObjects];
        //    Int32[] clusterItemCount = new Int32[numOfClusters];//this is used to calculate the mean(centroid) of each cluster
        //    double[][] sums = new double[numOfClusters][];
        //    int rndNumber;
            
        //    double objFuncVal = double.MaxValue;
        //    double [][] optimalCentroids = new double[numOfClusters][];

        //    //allocate memory
        //    for (int k = 0; k < optimalCentroids.Length; k++)
        //    {
        //        optimalCentroids[k] = new double[objects[0].Length];
        //    }

        //    //allocate memory
        //    for (int i = 0; i < sums.Length; i++)
        //    {
        //        sums[i] = new double[objects[0].Length];
        //    }


        //    //this for will find the optimal centroids
        //    for (int t = 0; t < 10; t++)
        //    {
        //        Array.Clear(clusterItemCount, 0, clusterItemCount.Length);

        //            for (int i = 0; i < numOfObjects; i++)
        //            {
        //                rndNumber = rnd.Next(0, numOfClusters);
        //                clustering[i] = rndNumber;
        //                clusterItemCount[rndNumber]++; //count for each cluster how many objects belong to it
        //            }
 
        //            //calculate the means for each cluster : first calculate the sums  
        //            for (int i = 0; i < clustering.Length; i++)
        //            {
        //                for (int j = 0; j < sums[clustering[i]].Length; j++)
        //                {
        //                    sums[clustering[i]][j] += objects[i][j];
        //                }
        //            }

        //            // divide by the number of objects in each cluster
        //            for (int i = 0; i < sums.Length; i++)
        //            {
        //                for (int j = 0; j < sums[i].Length; j++)
        //                {
        //                    if (clusterItemCount[i] == 0) //there is no items in this cluster! (can't divide by zero)
        //                    {
        //                        sums[i][j] = -1;
        //                    }
        //                    else
        //                    {
        //                        sums[i][j] /= clusterItemCount[i];
        //                    }
        //                }
        //            }
               
        //        double curObjFuncVal = AssignObjects(objects, sums, ref clustering, ref clusterItemCount);
        //        if (curObjFuncVal < objFuncVal)
        //        {
        //            objFuncVal = curObjFuncVal;


        //            for (int i = 0; i < sums.Length; i++)
        //            {
        //                Array.Copy(sums[i], optimalCentroids[i],sums[i].Length );
        //                Array.Clear(sums[i], 0, sums[i].Length);
        //            }
                
        //        }

        //    }//for


        //    //now copy the means to the centroids array

        //    for (int i = 0; i < sums.Length; i++)
        //    {
        //        Array.Copy(optimalCentroids[i], centroids[i], sums[i].Length);
        //    }

        //    return clustering;
        //}
        #endregion

        #region CalculateDistance
        /// <summary>
        ///  Calculates the eculidean distance from the <see cref="point"/> to the <see cref="centroid"/>
        /// </summary>
        private static double CalculateDistance(double[] item, double[] centroid)
        {
            // For each attribute calculate the squared difference between the centroid and the point
            double sum = 0;
            for (int i = 0; i < item.Length; i++)
                sum += Math.Pow(centroid[i] - item[i], 2);

            return Math.Sqrt(sum);
        }
        #endregion

        #region AllocateMemory
        public static double[][] AllocateMemory(int columns, int rows)
        {
            var matrix = new double[columns][];

            for (int i = 0; i < matrix.Length; i++)
                matrix[i] = new double[rows];

            return matrix;
        }
        #endregion

    }//MyKmeans

    #region class KMeansResults
    /// <summary>
    /// Represents a single result from the <see cref="KMeans"/> algorithm. 
    /// Contains the original items arranged into the clusters converged on as well as the centroids chosen and the total distance of the converged solution.
    /// </summary>
    /// <typeparam ></typeparam>
    public class KMeansResults
    {
        public double[][] Centroids { get; private set; }

        public int[] Clustering { get; private set; }

        public KMeansResults(double[][] centroids, int[] clustering )
        {
            Centroids = centroids;
            Clustering = clustering;
        }
    }
    #endregion

    #region class KmeansIterationResult
    public class KmeansIterationResult : IComparable<KmeansIterationResult>
    {
        public int iteration;

        public double[][] centroids;

        public double objFuncVal;

        public KmeansIterationResult(int numOfCentroids, int sizeOfCentroid)
        {
            centroids = MyKmeans.AllocateMemory(numOfCentroids, sizeOfCentroid);
            objFuncVal = 0;
        }

        #region IComparable<KmeansIterationResult> override
        public int CompareTo(KmeansIterationResult value)
        {
            return objFuncVal.CompareTo(value.objFuncVal);
        }
        #endregion
    } 
    #endregion


}
